package com.cty.thirteenthDay;

import java.util.Arrays;

//给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数
public class Q_15 {
    public static void main(String[] args) {

    }

    // 方法一:使用额外的数组 力扣官方题解 时间复杂度O(n) 空间复杂度O(n)
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[(i + k) % n] = nums[i];
        }
        // 将指定源数组中的数组从指定位置复制到目标数组的指定位置 意思 从arr的0索引开始复制 复制到nums的 0 ——> n的索引上
        System.arraycopy(arr, 0, nums, 0, n);
    }

    //方法二:（力扣官方题解）环形代替 一直替换 (i+k) % n 元素 直到回到最初的元素 外层遍历的次数是 an = bk （a是遍历的圈数 b是遍历到的元素）
    public static void rotate2(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        int count = gcd(k,n);
        for (int start = 0; start < count;start++) {
            int current = start;
            int pre = nums[start];
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = pre;
                pre = temp;
                current = next;
            } while (start != current);
        }
    }

    //
    public static int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }
}
